package com.zhouxianglh.p40;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 40. 组合总和 II
 * <p>
 * 先排序,方便剪枝
 *
 * @author zhouxianglh
 */
public class Solution {
    public static void main(String[] args) {
        // System.out.println(combinationSum2(new int[]{10, 1, 2, 7, 6, 1, 5}, 8));
        // System.out.println(combinationSum2(new int[]{1, 1, 2, 2, 2, 2, 5, 6, 7, 10}, 8));
        // System.out.println(combinationSum2(new int[]{}, 8));
        // System.out.println(combinationSum2(new int[]{1}, 8));
        System.out.println(combinationSum2(new int[]{2, 5, 2, 1, 2}, 5));
    }

    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (null == candidates || candidates.length == 0) {
            return result;
        }
        Arrays.sort(candidates);
        combinationSum2(candidates, target, 0, 0, new ArrayList<>(), result);
        return result;
    }

    public static void combinationSum2(int[] candidates, int target, int index, int nowCount, List<Integer> list,
                                       List<List<Integer>> result) {
        for (int i = index, j = candidates.length; i < j; i++) {
            int value = candidates[i];
            int newCount = value + nowCount;
            if (newCount == target) {
                List<Integer> values = new ArrayList<>(list);
                values.add(value);
                result.add(values);
                break;
            } else if (newCount > target) {
                break;
            } else {
                if (i > index && candidates[i] == candidates[i - 1]) {
                    continue;
                }
                List<Integer> values = new ArrayList<>(list);
                values.add(value);
                combinationSum2(candidates, target, i + 1, newCount, values, result);
            }
        }
    }
}
